Certain frequency bands such as the so-called ISM band near 2.4 GHz (for “Industrial, Scientific and Medical”) have been allocated and provided with established protocols that govern transmissions in a manner intended to permit the bandwidth to be shared by a number of simultaneous users. In particular, spread spectrum transmission of digital packet data is used, wherein transmitting and receiving apparatus hop from one frequency to another in a coordinated sequence that spreads the transmissions uniformly over the bandwidth. These frequencies are available for various wireless uses, including local area networks that can employ the same sort of client/server protocols and peer to peer transmissions that are also used for hard wired local area networks comprising a network server.
In a technology known as Bluetooth, a consortium of communications and data processing companies have proposed a standard for use of these frequencies to establish ad-hoc short range wireless networks in which mobile devices can couple together for data communications and also can couple as transients into fixed networks that support wireless access. This standard can make communication and digital data network services accessible to mobile devices in everyday use. Personal electronic devices, such as cellular telephones, pagers, personal digital assistants, laptop and “palm-top” computers, etc., can exchange data and participate in powerful and/or wide ranging networks, without the need for network cards, cables, connectors and interface software that typically are needed to couple a desktop computer to a local area network.
Ad-hoc and client/server networks can be made accessible under various standards and protocols, including but not limited to the Bluetooth standards, the somewhat more generalized IEEE standard 802.11, and other such communication protocols. Input, output, storage, communication and processing devices of a type normally coupled exclusively to network servers or directly to client terminals, such as printers, scanners and other such devices, can be made available generally to wireless devices, without the need to wire a client computer or other terminal apparatus to an associated network (or perhaps directly to the peripheral device). Personal electronic devices are thereby made capable of many new and expanded functions using this technology.
Two or more associations of devices (networks or piconets) occupy overlapping areas or otherwise share a resource by which the two or more such associations can interfere, by producing message packets that collide with one another. In the usual situation, two networks or piconets hop to the same frequency at the same time, although cross talk and other effects may produce collisions in other situations as well.
When plural devices communicate over a data communication network, the devices compete with one another for access to the network resources, particularly transmission time and bandwidth. Frequency hopping data communication schemes permit devices to transmit data on substantially random sequences of frequencies, thus spreading communications over the bandwidth. However the sender and the receiver must operate at the same frequency at the same time. “Random” access also generally means that various devices each can transmit data whenever they have data ready to transmit. As a result, two or more devices may transmit messages at the same time. Overlapping messages that interfere with one another are said to “collide.”
When two messages collide, it is possible that neither one will be received without errors. In that case both messages must be transmitted again at a later time. Sometimes one is received correctly and not the other. In networks subject to collisions (sometimes called contention networks), it may be possible for a prospective transmitting device to signal a targeted receiving device to expect a message having certain attributes (e.g., a stated length) and/or to warn other devices off, before attempting to transmit the message. It may also be necessary for a receiving device to signal some form of acknowledgment message back to the sender (ACK) after receipt of a message, such as a measure of the received message length, or parity check information, etc., which might be checked for accuracy. These procedures may be needed because of the possibility that a message transmitted on the contention network may not have been received due to a collision, and represent undesirable overhead.
Message or packet collisions can occur whenever a message transmission by one device affects reception of another message. A collision may occur when two devices having random access to transmit over a network medium happen to transmit messages on the same medium (e.g., the same carrier frequency or channel) at the same time. The messages effectively collide completely, even if the messages only overlapped slightly. For example, the trailing edge of a first message might overlap the leading edge of a second message and garble only the endmost bytes of the message. The sender and receiver cannot distinguish the error free part of the message from the rest.
Collisions also may occur due to less direct conflicts. For example, a transmission on an adjacent channel may interfere, or a reflected image or ghost of a transmitted message may interfere. A collision typically affects the reception of both overlapping messages, but it is possible that one message may overpower the other and one of the two colliding messages may be correctly received. The component bytes of the two colliding messages may be mixed or garbled such that one message cannot be distinguished from another by the receiver(s). If received at all, a data error may be detected by the receiver. The error may have occurred at an unknown position in the message, rendering the error uncorrectable. Both colliding messages are transmitted again.
It is generally considered efficient to permit devices on a network to have relatively free random access to transmit. Some level of contention is generally tolerated in the interest of efficiency, and where necessary, messages subject to collision are resent. Message contention reduces the message throughput of a network. The effect of contention on throughput may be trivial when traffic is light and collisions are unlikely. Load on the throughput due to contention can become severe if traffic is heavy. In a heavy traffic situation, re-transmissions necessitated by frequent collisions increase the traffic and make additional collisions likely, requiring more re-transmissions. With very heavy traffic, the network bandwidth could theoretically all be consumed by unsuccessful colliding messages and colliding re-transmissions that result.
What is needed is a method and apparatus that facilitates efficient communications among the devices that participate in such a network. Advantageously, the communications should be only loosely regulated for maximum versatility, while adhering to rules under which bandwidth is shared. The rules and protocols should either minimize the incidence of message collisions or minimize their adverse effects. Preventing collisions can be expected to decrease the extent of regulation needed which tends to slow down communications, or avoid a centralized controller for allocating time slots thus minimizing collisions.